package a2023.a1013;

import java.util.*;

/**
 * @author lenovo
 * @date 2023/10/13
 */
public class a {
    public static void main(String[] args) {
        System.out.println(avoidFlood(new int[]{1,2,0,1,2}));
    }


    //    public static int[] avoidFlood(int[] rains) {
//        int length = rains.length;
//        int[] ints = new int[length];
//        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//        List<Integer> list = new ArrayList<Integer>();
//        for (int i = 0; i < length; i++) {
//            int rain = rains[i];
//            if (rain == 0) {
//                list.add(i);
//            } else {
//                ints[i] = -1;
//                if (map.containsKey(rain)) {
//                    if (list.size() > 0) {
//                        ints[list.get(0)] = rain;
//                        list.remove(0);
//                        map.remove(rain);
//                    } else {
//                        return new int[0];
//                    }
//                } else {
//                    map.put(rain, i);
//                }
//            }
//        }
//        ints = Arrays.stream(ints)
//                .map(num -> num == 0 ? 1 : num)
//                .toArray();
//        return ints;
//    }
    public static int[] avoidFlood(int[] rains) {
        int[] ans = new int[rains.length];
        Arrays.fill(ans, 1);
        TreeSet<Integer> st = new TreeSet<Integer>();
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for (int i = 0; i < rains.length; ++i) {
            if (rains[i] == 0) {
                st.add(i);
            } else {
                ans[i] = -1;
                if (mp.containsKey(rains[i])) {
                    Integer it = st.ceiling(mp.get(rains[i]));
                    if (it == null) {
                        return new int[0];
                    }
                    ans[it] = rains[i];
                    st.remove(it);
                }
                mp.put(rains[i], i);
            }
        }
        return ans;
    }
}
